using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using NUnit.Framework;
using ProjectEuler.Core.Helpers;

namespace ProjectEuler.Core
{
    public class Problem26 : IProjectEulerProblem
    {
        public int Number
        {
            get { return 26; }
        }

        public string Description
        {
            get
            {
                return "Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.";
            }
        }

        public string Answer
        {
            get
            {
                return GetLongestCycleUnitFractionDenominator().ToString();
            }
        }

        // "No simple general formula to compute primitive roots modulo n is known"
        // it is way too much work to get these, but fortunately Wikipedia lists all of them under 1000 (how convenient)
        private const string _primesWithPrimitiveRootModulo10 =
            "7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983";

        private static IEnumerable<int> PrimesWithPrimitiveRootModulo10
        {
            get
            {
                return _primesWithPrimitiveRootModulo10.Split(',').Select(i => int.Parse(i)).ToList();
            }
        }

        // repeating decimals are just cyclic numbers with with a decimal point in front
        // there's a formula to find a cyclic number given a prime and number base (see CyclicNumber method)
        // so all we have to do is go through each prime under 1000 and get the longest Cyclic
        // however, it's not that straightforward: some primes don't return a cyclic, only primes
        // with a primitive root modulo 10 do, so just loop through those
        //
        // for more information, see http://en.wikipedia.org/wiki/Cyclic_number and http://en.wikipedia.org/wiki/Primitive_root_modulo_n
        protected int GetLongestCycleUnitFractionDenominator()
        {
            var longestLength = 0;
            var longest = 7;
            foreach (var i in PrimesWithPrimitiveRootModulo10)
            {
                if (MathHelper.IsPrime(i))
                {
                    var cyclic = CyclicNumber(i);
                    if (cyclic.ToString().Length > longestLength)
                    {
                        longestLength = cyclic.ToString().Length;
                        longest = i;
                    }
                }
            }
            return longest;
        }

        // given a prime (p) and a number base (always going to be 10 for this problem)
        // then this method returns a cyclic numbe
        // (b^(p-1)) - 1  /  p
        protected BigInteger CyclicNumber(int prime)
        {
            const int numberBase = 10;
            var result = (BigInteger.Pow(numberBase, prime - 1) - 1)/(new BigInteger(prime));
            return result;
        }
    }

    [TestFixture]
    public class Problem26Tests : Problem26
    {
        [Test]
        public void CyclicNumber_with_a_prime_of_7_gives_142857()
        {
            // 1/7 = 142857 (given by Project Euler problem description)
            Assert.AreEqual(142857, CyclicNumber(7));
        }
    }
}
